//迷宫地图
const MAZE = [
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
];
Array.prototype.remove = function (cur) {
    let ctx = this;
    for (let i = 0; i < ctx.length; i++) {
        if (ctx[i] === cur) {
            ctx.splice(i, 1);
            break;
        }
    }
    return ctx;
};

/**
 * A*寻路主逻辑
 * @param {*} start 迷宫起点
 * @param {*} end 迷宫终点
 */
function aStarSearch(start, end) {
    let openList = new Array(); // 数组栈结构,可到达的格子
    let closeList = new Array(); // 已到达的格子
    // 把起点加入 openList
    openList.push(start);
    //主循环，每一轮检查1个当前方格节点
    while (openList.length > 0) {
        // 在openList中查找 F值最小的节点，将其作为当前方格节点
        let currentGrid = findMinGird(openList);

        // 将当前方格节点从openList中移除
        openList.remove(currentGrid);

        // 当前方格节点进入 closeList
        closeList.push(currentGrid);

        //  找到所有邻近节点
        let neighbors = findNeighbors(currentGrid, openList, closeList);
        /** 判断每个临近节点是否在openList中 */
        for (let i = 0; i < neighbors.length; i++) {
            let grid = neighbors[i];
            if (!openList.includes(grid)) {
                // 邻近节点不在openList 中，标记“父节点”、G、H、F，并放入openList
                grid.initGrid(currentGrid, end);
                openList.push(grid);
            }
        }

        //如果终点在openList中，直接返回终点格子
        for (let i = 0; i < openList.length; i++) {
            let grid = openList[i];
            if (grid.x == end.x && grid.y == end.y) {
                return grid;
            }
        }
    }
    //openList用尽，仍然找不到终点，说明终点不可到达，返回空
    return null;
}

function findNeighbors(grid, openList, closeList) {
    let gridList = new Array();
    if (isValidGrid(grid.x, grid.y - 1, openList, closeList)) {
        // 上
        gridList.push(new Grid(grid.x, grid.y - 1));
    }
    if (isValidGrid(grid.x, grid.y + 1, openList, closeList)) {
        // 下
        gridList.push(new Grid(grid.x, grid.y + 1));
    }
    if (isValidGrid(grid.x - 1, grid.y, openList, closeList)) {
        // 左
        gridList.push(new Grid(grid.x - 1, grid.y));
    }
    if (isValidGrid(grid.x + 1, grid.y, openList, closeList)) {
        // 右
        gridList.push(new Grid(grid.x + 1, grid.y));
    }

    return gridList;
}
/**
 * 验证节点是否有效
 * @param {*} x
 * @param {*} y
 * @param {*} openList
 * @param {*} closeList
 */
function isValidGrid(x, y, openList, closeList) {
    // 是否超过边界
    if (x < 0 || x >= MAZE.length || y < 0 || y >= MAZE[0].length) {
        return false;
    }
    // 是否有障碍物
    if (MAZE[x][y] == 1) {
        return false;
    }
    //是否已经在openList中
    if (containGrid(openList, x, y)) {
        return false;
    }
    //是否已经在closeList 中
    if (containGrid(closeList, x, y)) {
        return false;
    }
    return true;
}
/**
 * 判断对值是否在表格内
 * @param {*} grids
 * @param {*} x
 * @param {*} y
 */
function containGrid(grids, x, y) {
    for (let i = 0; i < grids.length; i++) {
        let n = grids[i];
        if (n.x == x && n.y == y) {
            return true;
        }
    }
    return false;
}
/**
 * 找列表中所有节点的最小值
 * @param {*} openList
 */
function findMinGird(openList) {
    let tempGrid = openList[0];
    for (let i = 0; i < openList.length; i++) {
        let grid = openList[i];
        if (grid.f < tempGrid.f) {
            tempGrid = grid;
        }
    }
    return tempGrid;
}

class Grid {
    constructor(x, y) {
        this.f = null;
        this.g = null;
        this.h = null;
        this.parent = null;
        this.x = x;
        this.y = y;
    }
    // 放入oppenList中
    initGrid(parent, end) {
        this.parent = parent;
        if (parent != null) {
            this.g = parent.g + 1; // x方向走一步
        } else {
            this.g = 1;
        }
        this.h = Math.abs(this.x - end.x) + Math.abs(this.y - end.y);
        this.f = this.g + this.h;
    }
}

// 设置起点和终点
let startGrid = new Grid(2, 1);
let endGrid = new Grid(2, 5);

// 搜索迷宫终点
let resultGrid = aStarSearch(startGrid, endGrid);

// 回溯迷宫路径
let path = new Array();
while (resultGrid != null) {
    path.push(new Grid(resultGrid.x, resultGrid.y));
    resultGrid = resultGrid.parent;
}
/**
 * 递归创建多维数组
 * @param  {...any} dimentions
 */
function creatMulitArray(...dimentions) {
    const [layer, ...d] = dimentions;
    return d.length
        ? Array(layer)
              .fill(0)
              .map((_) => creatMulitArray(...d))
        : Array(layer);
}
// 输出迷宫和路径，路径用*表示
let MAZEN = creatMulitArray(MAZE.length, MAZE[0].length);

for (let i = 0; i < MAZE.length; i++) {
    for (let j = 0; j < MAZE[0].length; j++) {
        if (containGrid(path, i, j)) {
            MAZEN[i][j] = '*';
        } else {
            MAZEN[i][j] = MAZE[i][j] + '';
            // console.log(MAZE[i][j] + ", ")
        }
    }
}
console.log(JSON.stringify(MAZEN));
